package com.bo.day20231128;

import java.util.Arrays;

/**
 * 荷兰国旗问题
 * 给你一个数组和一个目标数x,需要你实现 数组中的数小于等x 放在左边, 大于x的放在右边
 * 解题思路：
 * 两个指针,小于等于x的指针,数组指针
 * 小于等于x的指针,一开始放在最左边
 * 当数组指针上的数小于等于x时候,与小于等于x的指针+1的位置交换
 * 大于的情况在数组指针继续往下走
 * 最后结果就是,小于等于x的指针会把大于x的数组推到右边
 *
 * @Author: gpb
 * @Date: 2023/11/29 19:20
 * @Description:
 */
public class QuickSortRecursiveAndUnrecursive {

    /**
     * 荷兰国旗问题升级版本 左 <= x, 右 > x
     * 给你一个数组和数组最后一个数x做比较,需要你实现 数组中的数小于等于x 放在左边, 大于x的放在右边,最后一个等于x的数放在中间
     * 解题思路：
     * 两个指针,小于等于x的指针(左边-1位置),数组指针(左边起始位置)
     * 当数组指针上的数小于等于x时候,与小于等于x的指针+1的位置交换,指针往后移动
     * 大于的情况在数组指针继续往下走,最后把数组最后一个位置的数和小于等于x的指针+1位置进行交换
     * 最后结果就是,小于等于x的指针会把大于x的数组推到右边
     *
     * @param arr 数组
     * @param l   开始位置
     * @param r   结束位置
     * @return 返回中间x下标范围
     */
    public static int[] netherlandsFlag (int[] arr, int l, int r) {
        if (arr == null) {
            return new int[]{-1, -1};
        }
        if (l == r) {
            return new int[]{l, r};
        }
        // 定义小于等于x指针
        int less = l - 1;
        // 开始指针,等于l
        int index = l;
        while (index < r) {
            if (arr[index] <= arr[r]) {
                // 当数组指针上的数小于等于x时候,与小于等于x的指针+1的位置交换,指针往后移动
                swap(arr, index, ++less);
            }
            System.out.println("index=" + index + "less=" + less + "arr=" + Arrays.toString(arr));
            index++;
        }
        // 最后一个等于x的数放在中间
        swap(arr, r, ++less);
        System.out.println("index=" + index + "less=" + less + "arr=" + Arrays.toString(arr));
        return new int[]{less, less};
    }

    /**
     * 荷兰国旗问题升级版本 演进版本2
     * 给你一个数组和数组中最后一位置的数为x进行比较,需要你实现 数组中的数小于x 放在左边, 大于x的放在右边,等于x放在中间
     * 解题思路：
     * 三个指针,小于x的指针,数组指针,大于x的指针
     * 三种情况
     * 小于x的时候：与小于x的指针+1的位置交换,指针往后移动
     * 等于x的时候：小于x指针位置不动,数组指针往后移动
     * 大于x的时候：与大于x的指针交换位置,大于指针往左移动,然后和x做比较,如果小于x,与小于x的指针+1的位置交换,指针往后移动
     * 当数组指针和大于x指针相遇的时候,结束
     *
     * @param arr 数组
     * @param l   开始位置
     * @param r   结束位置
     * @return 返回中间x下标范围
     */
    public static int[] netherlandsFlagLast (int[] arr, int l, int r) {
        if (arr == null) {
            return new int[]{-1, -1};
        }
        if (l == r) {
            return new int[]{l, r};
        }
        // 小于x的指针,往右边移动
        int less = l - 1;
        // 大于x的指针,往左边移动
        int more = r;
        int index = l;
        // 当前位置，不能和 >区的左边界撞上
        while (index < more) {
            if (arr[index] == arr[r]) {
                // 数组指针往后移动
                index++;
            } else if (arr[index] < arr[r]) {
                // 数组当前指针与小于x的指针+1的位置交换,指针往后移动
                swap(arr, index++, ++less);
            } else {
                // 大于情况下
                // 和大于x指针-1,交换
                swap(arr, index, --more);
            }
            System.out.println("index=" + index + "less=" + less + "more=" + more + "arr=" + Arrays.toString(arr));
        }
        // 最后一个等于x的数放在中间
        // // <[R]   =[R]   >[R]
        swap(arr, r, more);
        return new int[]{less + 1, more};
    }

    public static void swap (int[] arr, int l, int r) {
        int t = arr[l];
        arr[l] = arr[r];
        arr[r] = t;
        // 也可以使用^操作
//        arr[l] = arr[l] ^ arr[r];
//        arr[r] = arr[l] ^ arr[r];
//        arr[l] = arr[l] ^ arr[r];
    }

    public static void main (String[] args) {
        int[] arr1 = {8, 3, 5, 1, 2, 3, 8, 3};
        netherlandsFlagLast(arr1, 0, arr1.length - 1);
//        int[] arr = {3, 6, 2, 9, 7, 1, 4, 2, 5, 5, 2, 5};
//        int[] ints = netherlandsFlagLast(arr, 0, arr.length - 1);
//        System.out.println(Arrays.toString(arr));
//        System.out.println(Arrays.toString(ints));
//        netherlandsFlag(arr, 5);
//        System.out.println(Arrays.toString(arr));
//        netherlandsFlag2(arr, 5);
//        System.out.println(Arrays.toString(arr));
    }


    /**
     * 荷兰国旗问题 演进版本1
     * 给你一个数组和一个目标数x,需要你实现 数组中的数小于等于x 放在左边, 大于x的放在右边
     * 解题思路：
     * 两个指针,小于等于x的指针,数组指针
     * 小于等于x的指针,一开始放在最左边
     * 当数组指针上的数小于等于x时候,与小于等于x的指针+1的位置交换,指针往后移动
     * 大于的情况在数组指针继续往下走
     * 最后结果就是,小于等于x的指针会把大于x的数组推到右边
     *
     * @Author: gpb
     * @Date: 2023/11/29 19:20
     * @Description:
     */
    public static void netherlandsFlag1 (int[] arr, int x) {
        if (arr == null) {
            return;
        }
        // 小于等于x的指针范围
        int l = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= x) {
                swap(arr, i, ++l);
            }
        }
    }

    /**
     * 荷兰国旗问题升级版本 演进版本2
     * 给你一个数组和一个目标数x,需要你实现 数组中的数小于x 放在左边, 大于x的放在右边,等于x放在中间
     * 解题思路：
     * 三个指针,小于x的指针,数组指针,大于x的指针
     * 三种情况
     * 小于x的时候：与小于x的指针+1的位置交换,指针往后移动
     * 等于x的时候：小于x指针位置不动,数组指针往后移动
     * 大于x的时候：与大于x的指针交换位置,大于指针往左移动,然后和x做比较,如果小于x,与小于x的指针+1的位置交换,指针往后移动
     * 当数组指针和大于x指针相遇的时候,结束
     *
     * @param arr
     * @param x
     */
    public static void netherlandsFlag2 (int[] arr, int x) {
        if (arr == null) {
            return;
        }
        // 小于x的指针范围
        int l = -1;
        // 大于x的指针范围
        int r = arr.length;
        // 数组指针
        int i = 0;
        while (i < arr.length && i != r) {
            if (arr[i] < x) {
                // 小于x的时候：与小于x的指针+1的位置交换,指针往后移动
                swap(arr, i++, ++l);
            } else if (arr[i] > x) {
                // 大于x的时候：与大于x的指针交换位置,大于指针往左移动,然后和x做比较,如果小于x,与小于x的指针+1的位置交换,指针往后移动
                swap(arr, i, --r);
            } else {
                // 小于x指针位置不动,数组指针往后移动
                i++;
            }
        }
    }


}
